#pragma once
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>.
#include<assert.h>

typedef char QDatatype;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

// 10:40
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);




typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* ST = (MyStack*)malloc(sizeof(MyStack));
    if (ST == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    QueueInit(&ST->q1);
    QueueInit(&ST->q1);
    return ST;
}

void myStackPush(MyStack* obj, int x) {
    if (obj == NULL)
    {
        perror("malloc fail");
        return;
    }
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if (QueueEmpty(empty) != 0)
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }

    QueuePush(noempty, x);


}

int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if (QueueEmpty(empty) != 0)
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }

    while (noempty->size > 1)
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }

    int top = QueueFront(noempty);
    QueuePop(noempty);
    return top;
}

int myStackTop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if (QueueEmpty(empty) != 0)
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }

    return QueueBack(noempty);

}

bool myStackEmpty(MyStack* obj) {
    return !(QueueEmpty(&obj->q1) | QueueEmpty(&obj->q2));
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}



